﻿// 327. 玉米田.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>

using namespace std;


/*
http://poj.org/problem?id=3254

农夫约翰的土地由 M×N 个小方格组成，现在他要在土地里种植玉米。

非常遗憾，部分土地是不育的，无法种植。

而且，相邻的土地不能同时种植玉米，也就是说种植玉米的所有方格之间都不会有公共边缘。

现在给定土地的大小，请你求出共有多少种种植方法。

土地上什么都不种也算一种方法。

输入格式
第 1 行包含两个整数 M 和 N。

第 2..M+1 行：每行包含 N 个整数 0 或 1，用来描述整个土地的状况，1 表示该块土地肥沃，0 表示该块土地不育。

输出格式
输出总种植方法对 108 取模后的值。

数据范围
1≤M,N≤12
输入样例：
2 3
1 1 1
0 1 0
输出样例：
9
*/

#include <iostream>
#include <vector>

using namespace std;

int n, m;
const int N = 15, M = 1 << 12;
int field[N];

vector<int> state;
vector<int> Canget[M];

long long  dp[N][M];


bool Check(int x) {
	bool ret = false;

	for (int i = 0; i < m; i++) {
		if (((x >> i) & 1) && ((x >> (i + 1)) & 1)) {
			return ret;
		}
	}

	ret = true;
	return ret;
}

int main() {
	cin >> n >> m;

	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < m; j++) {
			int t; cin >> t;
			if (t == 0) {
				field[i] += 1 << j;
			}
		}
	}

	for (int i = 0; i < 1 << m; i++) {
		if (Check(i)) {
			state.push_back(i);
		}
	}

	for (int i = 0; i < state.size(); i++) {
		for (int j = 0; j < state.size(); j++) {
			int a = state[i]; int b = state[j];
			if ((a & b) == 0) {
				Canget[i].push_back(j);
			}
		}
	}
	dp[0][0] = 1;
	for (int i = 1; i <= n + 1; i++) {
		for (int j = 0; j < state.size(); j++) {
			int currState = state[j];
			if ((currState & field[i]) != 0) continue;
			for (int k = 0; k < Canget[j].size(); k++) {
				int prevStateidx = Canget[j][k];
				dp[i][j] += dp[i - 1][prevStateidx];
				dp[i][j] = dp[i][j] % 100000000;
			}
		}
	}

	cout << dp[n + 1][0] << endl;


	return 0;
}

